#include<bits/stdc++.h>

using namespace std;

int main() {
    int V, n;
    cin >> V >> n;
    int w[n], c[n];
    for (int i = 0; i < n; i++)cin >> w[i] >> c[i];
    int dp[V + 1000] = {0};
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = V; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
            ans = max(ans, dp[j]);
        }
    }
    cout << ans;

    return 0;
}